package pro.softzhang.algo.lc1000;

import com.alibaba.fastjson.JSON;
import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 *
 */
public class LC1048_LongestStringChain {
    public static void main(String[] args) {
        String[] ss = {"xbc","pcxbcf","xb","cxbc","pcxbc"};
        System.out.println(JSON.toJSONString(ss));
        // System.out.println(new Solution().longestStrChain(ss));
    }

    /**
     * 动态规划解法
     */
    @KDynamicPlanning
    static class Solution {
        public int longestStrChain(String[] words) {
            Arrays.sort(words, Comparator.comparingInt(String::length));
            Map<String, Integer> m = new HashMap<>();
            int longest = 0;
            for (String word : words) {
                m.put(word, 1);
                for(int i = 0; i < word.length(); i++) {
                    String prev = word.substring(0, i) + word.substring(i + 1);
                    if(m.containsKey(prev)) {
                        m.put(word, Math.max(m.get(word), m.get(prev) + 1));
                    }
                }
                longest = Math.max(longest, m.get(word));
            }
            return longest;
        }
    }
}
